import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class MaxInWindows {
    // 滑动窗口的最大值
    // https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        Deque<Integer> deque = new ArrayDeque<>();
        ArrayList<Integer> ret = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() <= i-size) {
                deque.pollFirst();
            }
            if (deque.isEmpty() || num[i] >= num[deque.peekFirst()]) {
                deque.addFirst(i);
            } else {
                while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                    deque.pollLast();
                }
                deque.addLast(i);
            }
            if (i >= size-1) {
                ret.add(num[deque.peekFirst()]);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        MaxInWindows maxInWindows = new MaxInWindows();
        int[] num = {2,3,4,2,6,2,5,1};
        System.out.println(maxInWindows.maxInWindows(num, 3));
    }
}
